1. Technical Field
The present invention relates generally to an improved data processing system, and particularly to an improved cache mechanism. Still more particularly, the present invention relates to an improved method and apparatus for completing I-MRU member protection within a cache.
2. Description of Related Art
Using one or more levels of caches to bridge the performance gap between a processor and main memory is a well established feature in data processing systems. When the processor issues a memory access request, the requests are first sent to the cache to determine whether the data or instructions requested are present in the cache memory. A “hit” occurs when the desired information is found in the cache. A “miss” occurs when a request or access to the cache does not produce the desired information. In response to a miss, one of the cache “lines” is replaced with a new one. The method to select a line to replace is called a replacement policy.
Caches often employ a set associative scheme by which the cache is partitioned into distinct classes of lines, wherein each class contains a small fixed number of lines. The classes of lines are usually referred to as “congruence classes.” The lines in a congruence class (which indicate the number of locations in which an address can reside) are usually referred to as sets in a set associative cache.
One generally used type of replacement policy is the least recently used (LRU) policy. An LRU policy is built upon the premise that the least recently used cache line in a congruence class is the least worthy of being retained. So, when it becomes necessary to evict a cache line to make room for a new one, an LRU policy chooses as a victim a cache line which is the least recently accessed set (or member) within a congruence class.
Within an LRU policy, two types of operations are typically carried out against the LRU state (which is maintained for each congruence class in a cache).
A most recently used-update (MRU-update) operation typically occurs due to a cache hit. The MRU-update adjusts the LRU state such that the “hit” member is ordered ahead of all other members in that congruence class, establishing the cache line in that member position as the most worthy member in the congruence class.
A least recently used-victim-selection (LRU-victim-selection) operation typically occurs when a cache miss requires that a member be allocated to hold a cache line arriving from elsewhere in the storage hierarchy. The operation determines which cache line is the least worthy of being retained in the congruence class, evicts that cache line, and places the newly arriving cache line in the member's position.
Several factors complicate the behavior of LRU replacement policies in multi-level cache hierarchies, particularly when those hierarchies contain nth level caches that are shared by multiple structures at level n−1. For example, a processor may contain a first level instruction cache and a first level data cache. These may be backed by a second level cache that includes both instructions and data. Such a structure is designed so that processor requests for cache lines that miss in the first level caches have a high likelihood of being found in the second level cache.
As described earlier, the LRU replacement policy in the first level caches would update as “most-recently-used” those cache lines that are used most often by the processor. Cache lines that are less important (or worthy) to the processor, since they are used less often, would be less likely to be marked as most-recently-used. Thus, the more frequently used lines tend to remain in the first level cache, while the less frequently used lines tend to be evicted from the first level cache.
The LRU policy in the second level cache would update as most-recently-used those cache lines that are requested from the second level cache when a first level cache miss occurs. These lines would tend to be those lines which were evicted from the first level cache, and are less worthy to the processor than the cache lines which tend to hit in the first level caches. Thus, the cache lines that most often are not found in the first level caches, but are repeatedly needed by the processor, are the cache lines most likely to remain in the second level cache, due to the fact that they are more likely to be beneficially affected by MRU-updates.
A large number of applications have a small instruction footprint and larger data requirements, resulting in “unbalanced” caching behaviors, wherein the instructions that are utilized most often by the processor are frequently evicted from the L2 cache. Thus, cache lines which are most worthy to the processor are less likely to benefit from MRU-updates in the second level cache, and hence, are more likely to be evicted from the second level cache than the cache lines which are less worthy to the processor.
Previous methods have been provided for protecting specific instructions required at the first level cache from being evicted from a second level (L2) cache. With these methods, the L2 cache LRU algorithm contains a pointer to protect the instruction most recently used (I-MRU) line for each congruence class in the L2 cache. This reserved ‘way’ is in place to prevent technical codes (with a small Instruction (“I”) footprint, but large data footprint) from “thrashing” the I footprint. This conventional method would essentially protect one full ‘way’ of the cache. For example ⅛ of an 8 way set associative cache would be reserved for instructions. In addition, the asymmetry of the remaining data ways combined with typical pseudo-lru algorithms produced sub optimal behavior for some workloads.
Therefore, the present invention recognizes that it would be advantageous to have an improved method, apparatus, and computer system for reducing the sub-optimal performance exhibited from the continued protection of old instructions lines that are currently protected via I-MRU policies from being evicted from a second level, inclusive cache.